package com.klun.project.common.constans.leetcode;


import java.util.Deque;
import java.util.List;
import java.util.Stack;

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
// 示例 1：
//输入：s = "()"
//输出：true
// 示例 2：
//输入：s = "()[]{}"
//输出：true
// 示例 3：
//输入：s = "(]"
//输出：false
// 提示：
// 1 <= s.length <= 104
// s 仅由括号 '()[]{}' 组成
// Related Topics 栈 字符串
// 👍 3586 👎 0
public class Solution20 {

	public boolean isValid(String s) {
		Stack<Character> stack0 = new Stack<>();
		for (char c : s.toCharArray()) {
			if (c == '(' || c == '[' || c == '{') stack0.push(c);
			if (c == ')' || c == ']' || c == '}') {
				if (stack0.isEmpty()) {
					return false;
				}
				char zuo = stack0.pop();
				if ((c == ')' && zuo == '(') ||
						(c == ']' && zuo == '[') ||
						(c == '}' && zuo == '{')) {
					continue;
				} else {
					return false;
				}
			}
		}
		if (stack0.isEmpty()) return true;
		return false;
	}

	public static void main(String[] args) {
		Solution20 solution = new Solution20();
		System.out.println(solution.isValid("()()([]{}{[]{])"));
	}


}
